#在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
# 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

import time

def get_input(lst,my_int):
    if len(lst)==0 or len(lst[0])==0:
        return False
    for i in lst:
        for j in i:
            if my_int==j:
                return True


    return False
# 这是一个最容易想到的做法，但是却没有用上数组元素的递增，所以不是最好的做法

my_lst = [[1,2,3],[4,5,6],[7,8,9]]
print(get_input(my_lst,9))



class Solution:
    # array 二维列表
    def Find(self, target, array):
        if len(array)==0 or len(array[0])==0:
            return False
        for i in range(len(array)-1,-1,-1):
            if array[i][0]>target or array[i][-1]<target:#这些比较，才是精华，一行当中最小的都比他大，后面就不必说了，可以极大地减少运算量
                continue
            for j in range(len(array[i])-1,-1,-1):
                if array[i][j]==target:
                    return True
                elif array[i][j]>target:
                    return False
        return False

sol = Solution()
print(sol.Find(10,my_lst))

